class Solution {
public:
    struct state{
        int x,y,dis;
        int flg;
        bool operator <(const state& p) const 
        {
            return dis>p.dis;
        }
    };
    int f[1000][1000]={0};
    int v[1000][1000]={0};
    int dx[4]={0,0,1,-1};
    int dy[4]={1,-1,0,0};
    int minTimeToReach(vector<vector<int>>& moveTime) {
        int n=moveTime.size(),m=moveTime[0].size();
        memset(f,0x3f3f3f,sizeof(f));

        priority_queue<state> q;
        f[0][0]=0;
        q.push({0,0,0,1});
        while(q.size())
        {
            state u=q.top();
            q.pop();
            if(v[u.x][u.y])
                continue;
            v[u.x][u.y]=1;
            for(int i=0;i<4;i++)
            {
                int nx=u.x+dx[i];
                int ny=u.y+dy[i];
                if(nx<0 || nx>=n || ny<0 || ny>=m || v[nx][ny])
                {
                    continue;
                }
                int dist=max(f[u.x][u.y],moveTime[nx][ny])+u.flg;
                if(f[nx][ny]>dist)
                {
                    f[nx][ny]=dist;
                    int t=u.flg==1?2:1;
                    q.push({nx,ny,dist,t});
                }
            }
        }
        return f[n-1][m-1];
    }
};
